package _05_二叉树;

import java.util.LinkedList;

public class _117_填充每个节点的下一个右侧节点指针II {

    public Node connect(Node root) {
        if (root == null) return root;
        // 广度优先搜索
        // 额外处理第一个节点
        root.next = null;
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            // 拿到左右节点
            if (node.left != null) {
                // 寻找下一个节点
                node.left.next = node.right != null ? node.right : findRemain(node.next);
                queue.offer(node.left);
            }
            if (node.right != null) {
                node.right.next = findRemain(node.next);
                queue.offer(node.right);
            }
        }
        return root;
    }

    // 寻找兄弟节点的下一个节点
    public Node findRemain(Node parent) {
        if (parent == null) return null;
        if (parent.left != null) return parent.left;
        else if (parent.right != null) return parent.right;
        else return findRemain(parent.next);
    }

}
